#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <string>
//class Solution {
//public:
//    string decodeString(string s) {
//        string ret;
//        int i = 0;
//        for (int i = 0; i < s.size();)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//                change(ret, s, i);
//            else
//                ret += s[i++];
//        }
//        return ret;
//    }
//    void change(string& tmp, string& s, int& i)
//    {
//        while (i < s.size())
//        {
//            if (s[i] == ']')
//            {
//                i++;
//                return;
//            }
//            else if (s[i] >= '0' && s[i] <= '9')
//            {
//                int num = 0;
//                while (s[i] >= '0' && s[i] <= '9')
//                {
//                    num = num * 10 + s[i++] - '0';
//                }
//                string tmp1;
//                i += 1;
//                while (i < s.size())
//                {
//                    if (s[i] >= '0' && s[i] <= '9')
//                    {
//                        change(tmp1, s, i);
//                    }
//                    else if (s[i] == ']')
//                        break;
//                    else
//                    {
//                        tmp1 += s[i++];
//                    }
//                }
//
//                while (num--)
//                {
//                    tmp += tmp1;
//                }
//            }
//            else
//            {
//                tmp += s[i++];
//            }
//
//        }
//    }
//};
#include <stack>
//class Solution {
//public:
//    string decodeString(string s) {
//        stack<char> st;
//        string ret;
//        for (int i = 0; i < s.size();)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                while (s[i] != ']')
//                {
//                    if (s[i] == '[')
//                        i++;
//                    else
//                        st.push(s[i++]);
//                }
//            }
//            else if (s[i] == ']')
//            {
//                string tmp;
//                while (s[i] == ']')
//                {
//                    int num = 0;
//                    //string tmp1;
//                    char top = st.top();
//                    while (!(top >= '0' && top <= '9'))
//                    {
//                        tmp += top;
//                        st.pop();
//                        top = st.top();
//                    }
//                    int j = 0;
//                    while (top >= '0' && top <= '9')
//                    {
//                        num = (top - '0') * pow(10, j) + num;
//                        st.pop();
//                        if (!st.empty())
//                        {
//                            top = st.top();
//                        }
//                        else
//                        {
//                            break;
//                        }
//
//                        j++;
//                    }
//                    string tmp1 = tmp;
//                    --num;
//                    while (num--)
//                    {
//                        tmp += tmp1;
//                    }
//                    i++;
//                }
//                reverse(tmp.begin(), tmp.end());
//                ret += tmp;
//            }
//            else
//            {
//                ret += s[i++];
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    string decodeString(string s) {
//        stack<string> st1;
//        stack<int> st2;
//        st1.push("");
//        for (int i = 0; i < s.size();)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                int num = 0;
//                while (s[i] >= '0' && s[i] <= '9')
//                {
//                    num = num * 10 + s[i++] - '0';
//                }
//                st1.push("");
//                st2.push(num);
//            }
//            else if (s[i] == '[')
//            {
//                i++;
//                string tmp;
//                while (s[i] >= 'a' && s[i] <= 'z')
//                {
//                    tmp += s[i++];
//                }
//                if (tmp != "")
//                    st1.top() += tmp;
//            }
//            else if (s[i] == ']')
//            {
//                int num = st2.top();
//                st2.pop();
//                string tmp = st1.top();
//                st1.pop();
//                while (num--)
//                {
//                    st1.top() += tmp;
//                }
//                i++;
//            }
//            else
//            {
//                string tmp;
//                while (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
//                {
//                    tmp += s[i++];
//                }
//                st1.top() += tmp;
//            }
//        }
//        string ret = st1.top();
//        return ret;
//    }
//};
//class Solution {
//public:
//    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
//        int popi = 0;
//        stack<int> st;
//        for (int i = 0; i < pushed.size(); i++)
//        {
//            st.push(pushed[i]);
//            while ((!st.empty()) && st.top() == popped[popi])
//            {
//                st.pop();
//                popi++;
//            }
//        }
//        return st.empty();
//    }
//};

#include <vector>
#include <queue>
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};


class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>>ret;
        queue<Node*> q;
        if (root)
            q.push(root);
        int num = 0;
        int num1 = 1;
        int count = 0;
        vector<int> tmp1;

        while (!q.empty())
        {
            Node* tmp = q.front();
            tmp1.push_back(tmp->val);
            q.pop();
            count++;
            for (int i = 0; i < (tmp->children).size(); i++)
            {
                if (tmp->children[i])
                {
                    cout << tmp->children[i]->val << " ";
                    q.push(tmp->children[i]);
                    num++;
                }
            }
            if (count == num1)
            {
                num1 = num;
                count = 0;
                num = 0;
                ret.push_back(tmp1);
                tmp1.clear();
            }
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ret;
        if (root)
            q.push(root);
        int count = 0;
        while (!q.empty())
        {
            int size = q.size();
            vector<int> tmp1;
            for (int i = 0; i < size; i++)
            {
                TreeNode* tmp = q.front();
                q.pop();
                tmp1.push_back(tmp->val);
                if (tmp->left)
                    q.push(tmp->left);
                if (tmp->right)
                    q.push(tmp->right);

            }
            if (count % 2 == 1)
            {
                reverse(tmp1.begin(), tmp1.end());
            }
            count++;
            ret.push_back(tmp1);
        }
        return ret;

    }
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        queue<pair<TreeNode*, unsigned int>> q;
        if (root)
            q.push(make_pair(root, 1));
        else
            return 0;
        int ret = 1;
        while (!q.empty())
        {
            int size = q.size();
            unsigned int begin = 0;
            unsigned int end = 0;
            for (int i = 0; i < size; i++)
            {
                TreeNode* tmp = q.front().first;
                long long pos = q.front().second;
                q.pop();
                if (tmp->left)
                {
                    q.push(make_pair(tmp->left, pos * 2 - 1));
                    if (begin == 0)
                        begin = pos * 2 - 1;
                    end = pos * 2 - 1;
                }
                if (tmp->right)
                {
                    q.push(make_pair(tmp->right, pos * 2));
                    if (begin == 0)
                        begin = pos * 2;
                    end = pos * 2;
                }
            }
            //cout<<begin<<":"<<end<<endl;
            ret = max(ret, (int)(end - begin + 1));
            //cout<<left<<":"<<right<<endl;
        }
        return ret;
    }
};
int main()
{
    Node* n1 = new Node(1);
    Node* n2 = new Node(3);
    Node* n3 = new Node(2);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);
    Node* n6 = new Node(6);
    n1->children.push_back(nullptr);
    n1->children.push_back(n2);
    n1->children.push_back(n3);
    n1->children.push_back(n4);
    n2->children.push_back(n5);
    n2->children.push_back(n6);
    Solution().levelOrder(n1);
    //cout << Solution().decodeString(string("2[abc]3[cd]ef")) << endl;
	return 0;
}